package com.qqn.kuangbiao.class3_20;

import java.util.Arrays;

/**
 * 二分查找
 * <a href="https://leetcode.cn/problems/binary-search/">...</a>
 * 题目:给你一个升序数组nums和一个目标值target，返回目标值target在数组nums中的下标，
 * 如果不存在则返回-1
 * 思路:题目中说了，是升序数组，那么就可以进行二分查找，
 * 二分时间复杂度是O(logN)，暴力是O(N)。至于二分是什么，边界如何处理，
 * 视频:<a href="https://www.bilibili.com/video/BV1fA4y10715/">...</a>
 */
public class algorithm01 {
    // mid 变量的定义争取最小作用域有效 所以尽量不要写在循环外面
    public static int search(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                R = mid - 1;
            } else if (nums[mid] < target) {
                L = mid + 1;
            }
        }
        return -1;
    }

    public static int[] generateArray(int maxValue, int maxSize) {
        int[] arr = new int[(int) (Math.random() * maxSize)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        int[] copy = new int[arr.length];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = arr[i];
        }
        return copy;
    }

    public static void sortArr(int[] arr) {
        Arrays.sort(arr);
    }

    public static void findIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                System.out.println("findIndex: " + i);
            }
        }
    }

    public static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxSize = 10000;
        int maxValue = 10000;
        int testTimes = 1;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateArray(maxValue, maxSize);
            sortArr(arr);
            int[] copyArr = copyArray(arr);
            // printArr(arr);
            // printArr(copyArr);
            // findIndex(copyArr, 12);
            // int index = search(arr, 12);
            int[] testArr = new int[]{2, 5};
            findIndex(testArr, 0);
            int index = search(testArr, 5);
            System.out.println(index);
        }
    }
}
